[BZOJ4542]-大数

莫队

题目链接

首先！我们要提到一个模运算的性质：

然后就可以开始了。

$P \neq 2, 5$ 的情况：

要计算一个区间能否整除 P，是不可能的，我们可以这么转化：

首先，可以 $O(n)$ 预处理出 $S[i … n] % P$, 这要用到上面的性质。

如果 $S[l … n] - S[r + 1 … n] \equiv 0 (mod P)$, 那么 $S[l … r] \equiv 0 (mod P)$.

这样，问题就转化成了：求在 [L, R] 这个区间内，有多少个 S[i … n] % P 是相同的，其中 L <= i <= R. 莫队套路，是吧？

$P = 2, 5$ 的情况：

特判。

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 1e5 + 10;
ll P, a = 0, b[N], c[N], sum, cnt[N], ans[N];
int n, m, unit;
char s[N];
struct node {
    int l, r, id;
}q[N];

bool cmp(node a, node b) {
    return a.l / unit == b.l / unit ? a.r < b.r : a.l / unit < b.l / unit;
}

void update(int x, int t) {
    sum -= cnt[b[x]] * (cnt[b[x]] - 1) / 2;
    if (t) cnt[b[x]]++;
    else cnt[b[x]]--;
    sum += cnt[b[x]] * (cnt[b[x]] - 1) / 2;
}

void solve(int p) {
    for (int i = 1; i <= n; i++) {
        ans[i] = ans[i - 1];
        cnt[i] = cnt[i - 1];  // 此处的 cnt[i] 表示 1 ～ i 中有多少个 s[i] 是 P 的倍数
        if ((s[i] - '0') % p == 0) ans[i] += i, cnt[i]++;
    }
    scanf("%d", &m);
    for (int i = 1; i <= m; i++) {
        int l, r; scanf("%d%d", &l, &r);
        printf("%lld\n", ans[r] - ans[l - 1] - (cnt[r] - cnt[l - 1]) * (l - 1));
    }
}

int main() {
    scanf("%lld", &P);
    scanf("%s", s + 1);
    n = strlen(s + 1);
    if (P == 2 || P == 5) {
        solve(P); return 0;
    }
    ll Fac = 1;
    for (int i = n; i >= 1; i--) {
        b[i] = c[i] = a = (a + Fac * (s[i] - '0')) % P;
        Fac = Fac * 10 % P;
    }
    b[++n] = c[n] = 0;
    sort(c + 1, c + n + 1);
    int tot = unique(c + 1, c + n + 1) - c - 1;
    for (int i = 1; i <= n; i++) b[i] = lower_bound(c + 1, c + tot + 1, b[i]) - c;
    scanf("%d", &m);
    unit = (int)sqrt(n);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &q[i].l, &q[i].r);
        ++q[i].r;
        q[i].id = i;
    }
    sort(q + 1, q + m + 1, cmp);
    int L = 1, R = 0;
    for (int i = 1; i <= m; i++) {
        while (R < q[i].r) update(++R, 1);
        while (R > q[i].r) update(R--, 0);
        while (L > q[i].l) update(--L, 1);
        while (L < q[i].l) update(L++, 0);
        ans[q[i].id] = sum;
    }
    for (int i = 1; i <= m; i++) printf("%lld\n", ans[i]);
    return 0;
}